package com.itheima.leetcode.od.b.graph.dijkstra;

import com.itheima.datastructure.graph.Edge;
import com.itheima.datastructure.graph.Vertex;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.PriorityQueue;

/**
 * (B卷,200分)- 最小传输时延（Java & JS & Python）
 * <p>
 * 题目描述
 * <p>
 * 某通信网络中有N个网络结点，用1到N进行标识。网络通过一个有向无环图表示，其中图的边的值表示结点之间的消息传递时延。
 * <p>
 * 现给定相连节点之间的时延列表times[i]={u，v，w}，其中u表示源结点，v表示目的结点，w表示u和v之间的消息传递时延。
 * <p>
 * 请计算给定源结点到目的结点的最小传输时延，如果目的结点不可达，返回-1。
 * <p>
 * 注：
 * <p>
 * N的取值范围为[1，100];
 * 时延列表times的长度不超过6000，且 1 <= u,v <= N，0 <= w <= 100;
 * <p>
 * 输入描述
 * <p>
 * 输入的第一行为两个正整数，分别表示网络结点的个数N，以及时延列表的长度M，用空格分隔；
 * <p>
 * 接下来的M行为两个结点间的时延列表[u v w];
 * <p>
 * 输入的最后一行为两个正整数，分别表示源结点和目的结点。
 * <p>
 * <p>
 * <p>
 * 输出描述
 * <p>
 * 起点到终点得最小时延，不可达则返回-1
 * <p>
 * 用例
 * <p>
 * 输入	3 3
 * <p>
 * 1 2 11
 * <p>
 * 2 3 13
 * <p>
 * 1 3 50
 * <p>
 * 1 3
 * <p>
 * 输出	24
 * 说明	无
 */
public class MinimumTransmissionDelay {
    public static void main(String[] args) {
        /*Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();

        int[][] times = new int[m][3];
        for (int i = 0; i < m; i++) {
            times[i][0] = sc.nextInt();
            times[i][1] = sc.nextInt();
            times[i][2] = sc.nextInt();
        }

        int src = sc.nextInt();
        int dist = sc.nextInt();*/

        int n = 3;
        int m = 3;
        String input = "1 2 11\n2 3 13\n1 3 50";
        int[][] times = Arrays.stream(input.split("\n"))
                .map(s -> Arrays.stream(s.split(" "))
                        .mapToInt(Integer::parseInt)
                        .toArray())
                .toArray(int[][]::new);

        int src = 1;
        int dist = 3;

        System.out.println(getResult(n, times, src, dist));
        System.out.println(getResult2(n, times, src, dist));
    }

    public static int getResult(int n, int[][] times, int src, int tar) {
        HashMap<Integer, ArrayList<int[]>> graph = new HashMap<>();

        for (int[] time : times) {
            int u = time[0];
            int v = time[1];
            int w = time[2];
            graph.putIfAbsent(u, new ArrayList<>());
            graph.get(u).add(new int[]{v, w});
        }

        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;

        ArrayList<Integer> needCheck = new ArrayList<>();
        while (true) {
            boolean flag = false;

            if (graph.containsKey(src)) {
                for (int[] next : graph.get(src)) {
                    int v = next[0];
                    int w = next[1];
                    int newDist = dist[src] + w;

                    if (newDist >= dist[v]) {
                        continue;
                    }

                    dist[v] = newDist;

                    if (!needCheck.contains(v)) {
                        needCheck.add(v);
                        flag = true;
                    }
                }
            }

            if (needCheck.size() == 0) {
                break;
            }

            if (flag) {
                needCheck.sort((a, b) -> dist[a] - dist[b]);
            }

            src = needCheck.remove(0);
        }

        return dist[tar] == Integer.MAX_VALUE ? -1 : dist[tar];
    }

    /**
     * 迪克斯特拉 单源最短路径算法（DijkstraPriorityQueue）
     *
     * @param n
     * @param times
     * @param src
     * @param tar
     * @return
     */
    public static int getResult2(int n, int[][] times, int src, int tar) {
        HashMap<String, Vertex> graph = new HashMap<>();
        Arrays.stream(times)
                .forEach(ints -> {
                            graph.putIfAbsent(String.valueOf(ints[0]), new Vertex(String.valueOf(ints[0])));
                            graph.putIfAbsent(String.valueOf(ints[1]), new Vertex(String.valueOf(ints[1])));
                            graph.get(String.valueOf(ints[0])).edges.add(new Edge(graph.get(String.valueOf(ints[1])), ints[2]));
                        }
                );

        PriorityQueue<Vertex> queue = new PriorityQueue<>((a, b) -> a.dist - b.dist); // 顺序排列
        graph.get(String.valueOf(src)).dist = 0;
        graph.values().forEach(vertex -> queue.offer(vertex));

        while (!queue.isEmpty()) {
            // 3. 选取当前顶点
            Vertex curr = queue.peek();
            // 4. 更新当前顶点邻居距离
            if (!curr.visited) {
                updateNeighboursDist(curr, queue);
                curr.visited = true;
            }
            // 5. 移除当前顶点
            queue.poll();
        }

        int dist = graph.get(String.valueOf(tar)).dist;

        return dist == Integer.MAX_VALUE ? -1 : dist;
    }

    private static void updateNeighboursDist(Vertex curr, PriorityQueue<Vertex> queue) {
        for (Edge edge : curr.edges) {
            Vertex n = edge.linked;
            if (!n.visited) {
                int dist = curr.dist + edge.weight;
                if (dist < n.dist) {
                    n.dist = dist;
                    n.prev = curr;
                    queue.offer(n); // 重新加入顶点触发队列排序，队列会存在重复指针，但是元素唯一，visited = true 后不会重复调用此方法
                }
            }
        }
    }
}